package 贪心andDp.dp;

import java.util.Arrays;

import static java.lang.Math.max;

public class _01背包问题 {
    /*
        有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
            1≤n≤100
            1≤wi，vi≤100
            1≤W≤10000
        输入：
            n=4
            (w,v)={(2,3),(1,2),(3,4),(2,2)}
            W=5
        输出：
            7（选择第0，1，3号物品）
        因为对每个物品只有选和不选两种情况，所以这个问题称为01背包。
 */
    static int[] wi = {2, 1, 3, 2};
    static int[] vi = {3, 2, 4, 2};
    static int n = 4;//物品数量
    static int w = 5;//背包称重
    static int[][] rec;

    public static void main(String[] args) {
        int ww = w;
        int ans = dfs(0, ww);
        System.out.println(ans);
        rec = new int[n][w + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(rec[i], -1);
        }
        ww = w;
        ans = m(0, ww);
        System.out.println(ans);
        System.out.println(dp());
    }

    //普通递归，存在重复计算的问题，效率低
    private static int dfs(int i, int ww) {
        if (i == n) return 0; //没东西可选
        if (ww <= 0) return 0;//装不进去
        int v2 = dfs(i + 1, ww); // 不选择当前物品
        if (ww >= wi[i]) {
            int v1 = vi[i] + dfs(i + 1, ww - wi[i]); //选择当前物品
            return Math.max(v1, v2);
        } else {
            return v2;
        }
    }

    //记忆型递归，记录下已经算过的值，提升效率
    private static int m(int i, int ww) {
        if (i == n) return 0;
        if (ww <= 0) return 0;
        //计算之前做查询
        if (rec[i][ww] >= 0) {
            return rec[i][ww];
        }
        int ans;
        int v2 = m(i + 1, ww);
        if (ww >= wi[i]) {
            int v1 = vi[i] + m(i + 1, ww - wi[i]);
            ans = Math.max(v1, v2);
        } else {
            ans = v2;
        }
        //计算之后做记录
        rec[i][ww] = ans;
        return ans;
    }

    //动态规划
    //如果当前重量要拿，用剩余重量去上一行中找对应的值与当前值相加，如果当前重量不拿，直接找上一行该列的值
    //两着比较取最大值
    public static int dp() {
        int[][] dp = new int[n][w + 1];
        //初始化dp表格的第一行
        for (int i = 0; i < w + 1; i++) {
            //此时的i代表的是列
            if (i >= wi[0]) {  //当前重量可以拿
                dp[0][i] = vi[0];
            } else {
                dp[0][i] = 0;
            }
        }
        //从第二行开始初始化
        for (int i = 1; i < n; i++) {//i代表行
            for (int j = 0; j < w + 1; j++) {//j代表列
                if (j >= wi[i]) { //要得起
                    int i1 = vi[i] + dp[i - 1][j - wi[i]];  //选择当前物品，剩余容量去上一行对应的列找
                    int i2 = dp[i - 1][j];  //不选择当前物品，直接使用上一行对应的列的值
                    dp[i][j] = Math.max(i1, i2);
                } else {  //要不起
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][w];
    }
}
